package cn.bellychang.leetcode.question021;

/**
 * @author ChangLiang
 * @date 2021/2/5
 */
public class Solution3 {

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

        if (l1 == null) {
            return l2;
        }

        ListNode temp2 = l2;
        while (temp2 != null) {
            ListNode next2 = temp2.next;

            if (l1.val >= temp2.val) {
                temp2.next = l1;
                l1 = temp2;
            } else {
                ListNode temp1 = l1.next;
                ListNode prev = l1;
                // save prev  [head1..temp]都是< node的 或者 temp1为最后一个元素
                while (temp1 != null && temp1.val < temp2.val) {
                    prev = temp1;
                    temp1 = temp1.next;
                }
                prev.next = temp2;
                temp2.next = temp1;
            }
            temp2 = next2;
        }
        return l1;
    }



}
